{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Remove Max Number of Edges to Keep Graph Fully Traversable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxNumEdgesToRemove"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #保证图可完全遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>Alice 和 Bob 共有一个无向图，其中包含 n 个节点和 3&nbsp; 种类型的边：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>类型 1：只能由 Alice 遍历。</li>\n",
    "\t<li>类型 2：只能由 Bob 遍历。</li>\n",
    "\t<li>类型 3：Alice 和 Bob 都可以遍历。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <code>edges</code> ，其中 <code>edges[i] = [type<sub>i</sub>, u<sub>i</sub>, v<sub>i</sub>]</code>&nbsp;表示节点 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code> 之间存在类型为 <code>type<sub>i</sub></code> 的双向边。请你在保证图仍能够被 Alice和 Bob 完全遍历的前提下，找出可以删除的最大边数。如果从任何节点开始，Alice 和 Bob 都可以到达所有其他节点，则认为图是可以完全遍历的。</p>\n",
    "\n",
    "<p>返回可以删除的最大边数，如果 Alice 和 Bob 无法完全遍历图，则返回 -1 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/06/5510ex1.png\" style=\"height: 191px; width: 179px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, edges = [[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>如果删除<strong> </strong>[1,1,2] 和 [1,1,3] 这两条边，Alice 和 Bob 仍然可以完全遍历这个图。再删除任何其他的边都无法保证图可以完全遍历。所以可以删除的最大边数是 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/06/5510ex2.png\" style=\"height: 190px; width: 178px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, edges = [[3,1,2],[3,2,3],[1,1,4],[2,1,4]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>注意，删除任何一条边都会使 Alice 和 Bob 无法完全遍历这个图。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/09/06/5510ex3.png\" style=\"height: 190px; width: 178px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4, edges = [[3,2,3],[1,1,2],[2,3,4]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>在当前图中，Alice 无法从其他节点到达节点 4 。类似地，Bob 也不能达到节点 1 。因此，图无法完全遍历。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10^5</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= min(10^5, 3 * n * (n-1) / 2)</code></li>\n",
    "\t<li><code>edges[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= edges[i][0] &lt;= 3</code></li>\n",
    "\t<li><code>1 &lt;= edges[i][1] &lt; edges[i][2] &lt;= n</code></li>\n",
    "\t<li>所有元组 <code>(type<sub>i</sub>, u<sub>i</sub>, v<sub>i</sub>)</code> 互不相同</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [remove-max-number-of-edges-to-keep-graph-fully-traversable](https://leetcode.cn/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [remove-max-number-of-edges-to-keep-graph-fully-traversable](https://leetcode.cn/problems/remove-max-number-of-edges-to-keep-graph-fully-traversable/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[3,1,2],[3,2,3],[1,1,3],[1,2,4],[1,1,2],[2,3,4]]', '4\\n[[3,1,2],[3,2,3],[1,1,4],[2,1,4]]', '4\\n[[3,2,3],[1,1,2],[2,3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        UFA = UnionFind(n)\n",
    "        UFB = UnionFind(n)\n",
    "\n",
    "        # use common edge first\n",
    "        for type, u, v in edges:\n",
    "            if type == 3:\n",
    "                if UFA.unionSet(u-1, v-1):\n",
    "                    UFB.unionSet(u-1, v-1)\n",
    "                else:\n",
    "                    ans += 1\n",
    "        \n",
    "        # use exclusive edge next\n",
    "        for type, u, v in edges:\n",
    "            # Alice only edge\n",
    "            if (type == 1 and not UFA.unionSet(u-1, v-1)) or (type == 2 and not UFB.unionSet(u-1, v-1)):\n",
    "                ans += 1\n",
    "        \n",
    "        if UFA.numSets == UFB.numSets == 1:\n",
    "            return ans \n",
    "        \n",
    "        return -1 \n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int, m: int=None) -> None:\n",
    "        \"\"\"\n",
    "        build m disjoint sets from n nodes\n",
    "        T: O(N)\n",
    "        \"\"\"\n",
    "        self.parents = list(range(n))   \n",
    "        self.ranks = [0] * n            \n",
    "        self.numSets = n                # number of disjoint sets\n",
    "\n",
    "\n",
    "    \n",
    "    def findSet(self, i: int) -> int:\n",
    "        \"\"\"return root of node i's set\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "           path-compression  \n",
    "           Recursion\n",
    "        \"\"\"\n",
    "        if self.parents[i] == i:\n",
    "            return i\n",
    "        else:\n",
    "            self.parents[i] = self.findSet(self.parents[i])\n",
    "            return self.parents[i]\n",
    "        \n",
    "    \n",
    "    def unionSet(self, i: int, j: int) -> None:\n",
    "        \"\"\"若节点i和节点j来自2个不同的互斥集合，将两个集合合并 \n",
    "           union by rank   矮树作为高树的子树\n",
    "           T: amortized O(α(N))  effectively O(1)\n",
    "             first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        ip, jp = self.findSet(i), self.findSet(j)\n",
    "\n",
    "        # 若两个节点来自同一互斥集合，返回\n",
    "        if ip == jp:\n",
    "            return False \n",
    "\n",
    "        # 若A树矮，B树高，A树连到B树的根节点上，新树rank不变\n",
    "        if self.ranks[ip] < self.ranks[jp]:\n",
    "            self.parents[ip] = jp\n",
    "\n",
    "        # 若B树矮，A树高，B树连到A树的根节点上，新树rank不变\n",
    "        elif self.ranks[jp] < self.ranks[ip]:\n",
    "            self.parents[jp] = ip\n",
    "\n",
    "        # 若两树等高，任选一种方案，新树 rank +1\n",
    "        else:\n",
    "            self.parents[jp] = ip\n",
    "            self.ranks[ip] += 1\n",
    "\n",
    "        # 互斥集总数-1\n",
    "        self.numSets -= 1\n",
    "\n",
    "        return True\n",
    "    \n",
    "    def isSameSet(self, i: int, j: int) -> bool:\n",
    "        \"\"\"判断节点i和节点j是否属于同一集合\n",
    "           T: O(α(N) first O(N) then O(1)\n",
    "        \"\"\"\n",
    "        # path compression twice\n",
    "        return self.findSet(i) == self.findSet(j)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "                \n",
    "                ufb.unite(u, v)\n",
    "\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    ufb.unite(u, v)\n",
    "\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        uf1 = UF(n)\n",
    "        for edge in edges:\n",
    "            if edge[0] == 3:\n",
    "                valid = uf1.union(edge[1]-1, edge[2]-1)\n",
    "                if not valid:\n",
    "                    ans += 1\n",
    "        \n",
    "        uf2 = UF(1)\n",
    "        uf2.parent = uf1.parent[:]\n",
    "        uf2.count = uf1.count\n",
    "        for edge in edges:\n",
    "            if edge[0] == 1:\n",
    "                valid = uf1.union(edge[1]-1, edge[2]-1)\n",
    "                if not valid:\n",
    "                    ans += 1\n",
    "            elif edge[0] == 2:\n",
    "                valid = uf2.union(edge[1]-1, edge[2]-1)\n",
    "                if not valid:\n",
    "                    ans += 1\n",
    "        if uf1.count == 1 and uf2.count == 1:\n",
    "            return ans\n",
    "        return -1\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, N):\n",
    "        self.parent = list(range(N))\n",
    "        self.count = N\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx == ry:\n",
    "            return False\n",
    "        self.parent[rx] = ry\n",
    "        self.count -= 1\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    #因为alice已经在上一步链接过了，如果alice没有链接，因为是双向边，所以bob也没链接，这时候要unite一下bob的\n",
    "                    ufb.unite(u, v)\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    ufb.unite(u, v)\n",
    "\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v) or not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "                \n",
    "                \n",
    "\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    ufb.unite(u, v)\n",
    "\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.comp_cnt = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1 for _ in range(n)]\n",
    "    def find(self,x):\n",
    "        return x if self.fa[x]==x else self.find(self.fa[x])\n",
    "    def union(self,x,y)->bool:\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x]<self.sz[y]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "        self.comp_cnt-=1\n",
    "        return True\n",
    "    def connected(self,x,y)->bool:\n",
    "        x = self.findset(x)\n",
    "        y = self.findset(y)\n",
    "        return x==y\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa,ufb = UF(n),UF(n)\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            edges[i][1]-=1\n",
    "            edges[i][2]-=1\n",
    "        ans = 0\n",
    "        for t,x,y in edges:\n",
    "            if t==3:\n",
    "                if not ufa.union(x,y):\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    ufb.union(x,y)\n",
    "        for t,x,y in edges:\n",
    "            if t==1:\n",
    "                if not ufa.union(x,y):\n",
    "                    ans+=1\n",
    "            elif t==2:\n",
    "                if not ufb.union(x,y):\n",
    "                    ans+=1\n",
    "        if ufa.comp_cnt!=1 or ufb.comp_cnt!=1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data= [i for i in range(n+1)] \n",
    "        self.cnt= n \n",
    "    def find(self, x):\n",
    "        if x == self.data[x]:\n",
    "            return x \n",
    "        fx = self.data[x]\n",
    "        while fx != self.data[fx]:\n",
    "            fx = self.data[fx]\n",
    "        self.data[x] = fx \n",
    "        return fx \n",
    "    def un(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] = fx \n",
    "            self.cnt -= 1\n",
    "            return True \n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dsu1= DSU(n)\n",
    "        dsu2 = DSU(n)\n",
    "        #dsu3 = DSU(n) \n",
    "        cut = 0 \n",
    "        for t, u, v in edges:\n",
    "            if t== 3:\n",
    "                if not dsu1.un(u, v):\n",
    "                    cut += 1\n",
    "                dsu2.un(u, v) \n",
    "\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                if not dsu1.un(u,v):\n",
    "                    cut += 1\n",
    "            elif t== 2:\n",
    "                if not dsu2.un(u, v):\n",
    "                    cut += 1\n",
    "        if dsu1.cnt > 1 or dsu2.cnt > 1:\n",
    "            return -1 \n",
    "        return cut "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 并查集模板\n",
    "class UnionFind:\n",
    "    def __init__(self, n: int):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        # 当前连通分量数目\n",
    "        self.setCount = n\n",
    "    \n",
    "    def findset(self, x: int) -> int:\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.findset(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def unite(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        if x == y: # have same root\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x # ensure x has larger size\n",
    "        self.parent[y] = x # append shorter tree into longer one\n",
    "        self.size[x] += self.size[y]\n",
    "        self.setCount -= 1\n",
    "        return True\n",
    "    \n",
    "    def connected(self, x: int, y: int) -> bool:\n",
    "        x, y = self.findset(x), self.findset(y)\n",
    "        return x == y\n",
    "\n",
    "class Solution:\n",
    "    # 优先添加「公共边」的策略\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa, ufb = UnionFind(n), UnionFind(n)\n",
    "        ans = 0\n",
    "        \n",
    "        # 节点编号改为从 0 开始\n",
    "        for edge in edges:\n",
    "            edge[1] -= 1\n",
    "            edge[2] -= 1\n",
    "\n",
    "        # 公共边\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not ufa.unite(u, v): \n",
    "                    ans += 1 # u和v在一个set中\n",
    "                else: # u和v不在一个set中，在ufa、ufb中合并\n",
    "                    ufb.unite(u, v)\n",
    "\n",
    "        # 独占边\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                # Alice 独占边\n",
    "                if not ufa.unite(u, v):\n",
    "                    ans += 1\n",
    "            elif t == 2:\n",
    "                # Bob 独占边\n",
    "                if not ufb.unite(u, v):\n",
    "                    ans += 1\n",
    "\n",
    "        if ufa.setCount != 1 or ufb.setCount != 1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.comp_cnt = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1 for _ in range(n)]\n",
    "    def find(self,x):\n",
    "        # if self.fa[x]==x:\n",
    "        #     return self.fa[x]\n",
    "        # self.fa[x] = self.find(self.fa[x])\n",
    "        # return self.fa[x]\n",
    "        return x if self.fa[x]==x else self.find(self.fa[x])\n",
    "    def union(self,x,y)->bool:\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x]<self.sz[y]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "        self.comp_cnt-=1\n",
    "        return True\n",
    "    def connected(self,x,y)->bool:\n",
    "        x = self.findset(x)\n",
    "        y = self.findset(y)\n",
    "        return x==y\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa,ufb = UF(n),UF(n)\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            edges[i][1]-=1\n",
    "            edges[i][2]-=1\n",
    "        ans = 0\n",
    "        for t,x,y in edges:\n",
    "            if t==3:\n",
    "                if not ufa.union(x,y):\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    ufb.union(x,y)\n",
    "        for t,x,y in edges:\n",
    "            if t==1:\n",
    "                if not ufa.union(x,y):\n",
    "                    ans+=1\n",
    "            elif t==2:\n",
    "                if not ufb.union(x,y):\n",
    "                    ans+=1\n",
    "        if ufa.comp_cnt!=1 or ufb.comp_cnt!=1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        alice, bob = list(range(n+1)), list(range(n+1))\n",
    "        alice_cc, bob_cc = n, n\n",
    "\n",
    "        def find(parent, p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent, parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(parent, p, q):\n",
    "            pRoot = find(parent, p)\n",
    "            qRoot = find(parent, q)\n",
    "            if pRoot == qRoot:\n",
    "                return False\n",
    "            else:\n",
    "                parent[pRoot] = qRoot\n",
    "                return True\n",
    "        \n",
    "        res = 0\n",
    "        for type, p, q in edges:\n",
    "            if type == 3:\n",
    "                if union(alice, p, q):\n",
    "                    union(bob, p, q)\n",
    "                    alice_cc -= 1\n",
    "                    bob_cc -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        for type, p, q in edges:\n",
    "            if type == 1:\n",
    "                if union(alice, p, q):\n",
    "                    alice_cc -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "            elif type == 2:\n",
    "                if union(bob, p, q):\n",
    "                    bob_cc -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        if alice_cc > 1 or bob_cc > 1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data= [i for i in range(n+1)] \n",
    "        self.cnt= n \n",
    "    def find(self, x):\n",
    "        if x == self.data[x]:\n",
    "            return x \n",
    "        st = [x]\n",
    "        while st[-1] != self.data[st[-1]]:\n",
    "            st.append(self.data[st[-1]]) \n",
    "            #fx = self.data[fx]\n",
    "        fx = st.pop() \n",
    "        while st:\n",
    "            self.data[st[-1]] = fx \n",
    "            st.pop() \n",
    "        return fx \n",
    "    def un(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] = fx \n",
    "            self.cnt -= 1\n",
    "            return True \n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dsu1= DSU(n)\n",
    "        dsu2 = DSU(n)\n",
    "        #dsu3 = DSU(n) \n",
    "        cut = 0 \n",
    "        for t, u, v in edges:\n",
    "            if t== 3:\n",
    "                if not dsu1.un(u, v):\n",
    "                    cut += 1\n",
    "                dsu2.un(u, v) \n",
    "\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                if not dsu1.un(u,v):\n",
    "                    cut += 1\n",
    "            elif t== 2:\n",
    "                if not dsu2.un(u, v):\n",
    "                    cut += 1\n",
    "        if dsu1.cnt > 1 or dsu2.cnt > 1:\n",
    "            return -1 \n",
    "        return cut "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.parent = [i for i in range(size)]\n",
    "        self.rank = [0 for _ in range(size)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def get_uniq_p(self):\n",
    "        ll = []\n",
    "        for i in self.parent:\n",
    "            ll.append(self.find(i))\n",
    "        return ll\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "            elif self.rank[rootX] < self.rank[rootY]:\n",
    "                self.parent[rootX] = rootY\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        alice = UnionFind(n)\n",
    "        bob = UnionFind(n)\n",
    "        res = 0\n",
    "        for edge in edges:\n",
    "            if edge[0] == 3:\n",
    "                if alice.find(edge[1] - 1) != alice.find(edge[2] - 1):\n",
    "                    alice.union(edge[1] - 1, edge[2] - 1)\n",
    "                    bob.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for edge in edges:\n",
    "            if edge[0] == 1:\n",
    "                if alice.find(edge[1] - 1) != alice.find(edge[2] - 1):\n",
    "                    alice.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "            elif edge[0] == 2:\n",
    "                if bob.find(edge[1] - 1) != bob.find(edge[2] - 1):\n",
    "                    bob.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "        if len(set(alice.get_uniq_p())) != 1 or len(set(bob.get_uniq_p())) != 1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.parent = [i for i in range(size)]\n",
    "        self.rank = [0 for _ in range(size)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def get_uniq_p(self):\n",
    "        ll = []\n",
    "        for i in self.parent:\n",
    "            ll.append(self.find(i))\n",
    "        return ll\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "            elif self.rank[rootX] < self.rank[rootY]:\n",
    "                self.parent[rootX] = rootY\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        edges.sort(key=lambda x: x[0], reverse=True)\n",
    "        alice = UnionFind(n)\n",
    "        bob = UnionFind(n)\n",
    "        res = 0\n",
    "        for edge in edges:\n",
    "            if edge[0] == 3:\n",
    "                if alice.find(edge[1] - 1) != alice.find(edge[2] - 1):\n",
    "                    alice.union(edge[1] - 1, edge[2] - 1)\n",
    "                    bob.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for edge in edges:\n",
    "            if edge[0] == 1:\n",
    "                if alice.find(edge[1] - 1) != alice.find(edge[2] - 1):\n",
    "                    alice.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "            elif edge[0] == 2:\n",
    "                if bob.find(edge[1] - 1) != bob.find(edge[2] - 1):\n",
    "                    bob.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "        if len(set(alice.get_uniq_p())) != 1 or len(set(bob.get_uniq_p())) != 1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.parent = [i for i in range(size)]\n",
    "        self.rank = [0 for _ in range(size)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def get_uniq_p(self):\n",
    "        ll = []\n",
    "        for i in self.parent:\n",
    "            ll.append(self.find(i))\n",
    "        return ll\n",
    "\n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "\n",
    "        if rootX != rootY:\n",
    "            if self.rank[rootX] > self.rank[rootY]:\n",
    "                self.parent[rootY] = rootX\n",
    "            elif self.rank[rootX] < self.rank[rootY]:\n",
    "                self.parent[rootX] = rootY\n",
    "            else:\n",
    "                self.parent[rootY] = rootX\n",
    "                self.rank[rootX] += 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param edges:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        edges.sort(key=lambda x: x[0], reverse=True)\n",
    "        alice = UnionFind(n)\n",
    "        bob = UnionFind(n)\n",
    "        res = 0\n",
    "        for edge in edges:\n",
    "            if edge[0] == 3:\n",
    "                if alice.find(edge[1] - 1) != alice.find(edge[2] - 1):\n",
    "                    alice.union(edge[1] - 1, edge[2] - 1)\n",
    "                    bob.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for edge in edges:\n",
    "            if edge[0] == 1:\n",
    "                if alice.find(edge[1] - 1) != alice.find(edge[2] - 1):\n",
    "                    alice.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "            elif edge[0] == 2:\n",
    "                if bob.find(edge[1] - 1) != bob.find(edge[2] - 1):\n",
    "                    bob.union(edge[1] - 1, edge[2] - 1)\n",
    "                else:\n",
    "                    res += 1\n",
    "\n",
    "        if len(set(alice.get_uniq_p())) != 1 or len(set(bob.get_uniq_p())) != 1:\n",
    "            return -1\n",
    "        return res\n",
    "\n",
    "a = Solution()\n",
    "print(a.maxNumEdgesToRemove(4, [[3,1,2], [3,3,4], [1,1,3],[2,2,4]]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        uf = UF(n + 1)\n",
    "        ans = 0\n",
    "\n",
    "        for a in edges:\n",
    "            if a[0] == 3:\n",
    "                if not uf.connected(a[1],a[2]):\n",
    "                    uf.union(a[1], a[2])\n",
    "                else:\n",
    "                    ans += 1\n",
    "\n",
    "\n",
    "        uf1 = copy.deepcopy(uf)\n",
    "        for a in edges:\n",
    "            if a[0] == 1:\n",
    "                if uf.find(a[1]) != uf.find(a[2]):\n",
    "                    uf.union(a[1], a[2])\n",
    "                else:\n",
    "                    ans += 1\n",
    "\n",
    "        for a in edges:\n",
    "            if a[0] == 2:\n",
    "                if uf1.find(a[1]) != uf1.find(a[2]):\n",
    "                    uf1.union(a[1], a[2])\n",
    "                else:\n",
    "                    ans += 1\n",
    "\n",
    "        count = 0    \n",
    "        for i, n in enumerate(uf.par):\n",
    "            if i == n:\n",
    "                if count == 2:\n",
    "                    return -1\n",
    "                count += 1\n",
    "        count = 0\n",
    "\n",
    "        for i, n in enumerate(uf1.par):\n",
    "            if i == n:\n",
    "                if count == 2:\n",
    "                    return -1\n",
    "                count += 1\n",
    "        return ans\n",
    "        \n",
    "class UF:\n",
    "    def __init__(self, size):\n",
    "        self.par = [i for i in range(size)]\n",
    "    \n",
    "    def find(self, x):\n",
    "        if x != self.par[x]:\n",
    "            self.par[x] = self.find(self.par[x])\n",
    "        return self.par[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        if self.find(x) != self.find(y):\n",
    "            self.par[self.find(x)] = self.find(y)\n",
    "        \n",
    "    def connected(self, x, y):\n",
    "        return self.find(x) == self.find(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        ufd = UnionFind(n)\n",
    "        res = 0\n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 3:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        \n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 1:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        if ufd.setCount > 1:\n",
    "            return -1\n",
    "\n",
    "        ufd = UnionFind(n)\n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 3:\n",
    "                ufd.union(a, b)\n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 2:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        if ufd.setCount > 1:\n",
    "            return -1\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.setCount = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx == ry:\n",
    "            return \n",
    "        \n",
    "        if self.size[ry] > self.size[rx]:\n",
    "            rx, ry = ry, rx\n",
    "        self.parent[ry] = rx\n",
    "        self.size[rx] += self.size[ry]\n",
    "        self.setCount -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        ufd = UnionFind(n)\n",
    "        res = 0\n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 3:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        \n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 1:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        if ufd.setCount > 1:\n",
    "            return -1\n",
    "\n",
    "        ufd = UnionFind(n)\n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 3:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    continue\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        for t, a, b in edges:\n",
    "            a -= 1\n",
    "            b -= 1\n",
    "            if t == 2:\n",
    "                if ufd.find(a) == ufd.find(b):\n",
    "                    res += 1\n",
    "                else:\n",
    "                    ufd.union(a, b)\n",
    "        if ufd.setCount > 1:\n",
    "            return -1\n",
    "        return res\n",
    "\n",
    "class UnionFind:\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.parent = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.setCount = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx == ry:\n",
    "            return \n",
    "        \n",
    "        if self.size[ry] > self.size[rx]:\n",
    "            rx, ry = ry, rx\n",
    "        self.parent[ry] = rx\n",
    "        self.size[rx] += self.size[ry]\n",
    "        self.setCount -= 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 借助并查集按照人物遍历每一条边\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.father = [None] * (size+1)\n",
    "        self.num_of_sets = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.father[x] is None: return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        self.father[self.find(x)] = self.find(y)\n",
    "        self.num_of_sets -= 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        uf_alice = UnionFind(n)\n",
    "        uf_bob = UnionFind(n)\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 3:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 1:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "            if _type == 2:\n",
    "                if not uf_bob.is_connected(n1,n2):\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "\n",
    "        return -1 if uf_alice.num_of_sets * uf_bob.num_of_sets > 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        alice, bob = list(range(n+1)), list(range(n+1))\n",
    "        alice_cc, bob_cc = n, n\n",
    "\n",
    "        def find(parent, p):\n",
    "            if parent[p] != p:\n",
    "                parent[p] = find(parent, parent[p])\n",
    "            return parent[p]\n",
    "\n",
    "        def union(parent, p, q):\n",
    "            pRoot = find(parent, p)\n",
    "            qRoot = find(parent, q)\n",
    "            if pRoot == qRoot:\n",
    "                return False\n",
    "            else:\n",
    "                parent[pRoot] = qRoot\n",
    "                return True\n",
    "        \n",
    "        res = 0\n",
    "        for type, p, q in edges:\n",
    "            if type == 3:\n",
    "                if union(alice, p, q):\n",
    "                    union(bob, p, q)\n",
    "                    alice_cc -= 1\n",
    "                    bob_cc -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        for type, p, q in edges:\n",
    "            if type == 1:\n",
    "                if union(alice, p, q):\n",
    "                    alice_cc -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "            elif type == 2:\n",
    "                if union(bob, p, q):\n",
    "                    bob_cc -= 1\n",
    "                else:\n",
    "                    res += 1\n",
    "        if alice_cc > 1 or bob_cc > 1:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.fa = [None] * (size + 1)\n",
    "        self.num_of_sets = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.fa[x] is None:\n",
    "            return x\n",
    "        self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        self.fa[self.find(x)] = self.find(y)\n",
    "        self.num_of_sets -= 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        uf_alice = UnionFind(n)\n",
    "        uf_bob = UnionFind(n)\n",
    "        for t , a, b in edges:\n",
    "            if t == 3:\n",
    "                if not uf_alice.is_connected(a,b):\n",
    "                    uf_alice.merge(a,b)\n",
    "                    uf_bob.merge(a,b)\n",
    "                else:\n",
    "                    res +=1\n",
    "\n",
    "        for t , a, b in edges:\n",
    "            if t == 1:\n",
    "                if not uf_alice.is_connected(a,b):\n",
    "                    uf_alice.merge(a,b)\n",
    "                else:\n",
    "                    res +=1\n",
    "            elif t == 2:\n",
    "                if not uf_bob.is_connected(a,b):\n",
    "                    uf_bob.merge(a,b)\n",
    "                else:\n",
    "                    res +=1\n",
    "        return -1 if uf_alice.num_of_sets * uf_bob.num_of_sets > 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.father = [None] * (size+1)\n",
    "        self.num_of_sets = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.father[x] is None: return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        self.father[self.find(x)] = self.find(y)\n",
    "        self.num_of_sets -= 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        uf_alice = UnionFind(n)\n",
    "        uf_bob = UnionFind(n)\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 3:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 1:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "            if _type == 2:\n",
    "                if not uf_bob.is_connected(n1,n2):\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "\n",
    "        return -1 if uf_alice.num_of_sets * uf_bob.num_of_sets > 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [1] * n\n",
    "\n",
    "    def find(self, u):\n",
    "        if self.parent[u] == u:\n",
    "            return u\n",
    "        self.parent[u] = self.find(self.parent[u])\n",
    "        return self.parent[u]\n",
    "\n",
    "    def merge(self, u, v):\n",
    "        u = self.find(u)\n",
    "        v = self.find(v)\n",
    "        if u == v:\n",
    "            return False\n",
    "        if self.rank[u] > self.rank[v]:\n",
    "            u, v = v, u\n",
    "        self.parent[u] = v\n",
    "        if self.rank[u] == self.rank[v]:\n",
    "            self.rank[v] += 1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        alice = UnionFind(n)\n",
    "        bob = UnionFind(n)\n",
    "        cnt = 0  # Number of edges removed\n",
    "\n",
    "        # Step 2: Add type 3 edges to both Alice and Bob\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if not alice.merge(u-1, v-1):\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    bob.merge(u-1, v-1)\n",
    "\n",
    "        # Step 3: Add type 1 and type 2 edges\n",
    "        for t, u, v in edges:\n",
    "            if t == 1 and not alice.merge(u-1, v-1):\n",
    "                cnt += 1\n",
    "            if t == 2 and not bob.merge(u-1, v-1):\n",
    "                cnt += 1\n",
    "\n",
    "        # Step 4: Check if Alice and Bob can traverse the graph completely\n",
    "        if len(set(alice.find(i) for i in range(n))) > 1 or len(set(bob.find(i) for i in range(n))) > 1:\n",
    "            return -1\n",
    "\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        uf_alice = UnionFind(n)\n",
    "        uf_bob = UnionFind(n)\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 3:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 1:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "            if _type == 2:\n",
    "                if not uf_bob.is_connected(n1,n2):\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "\n",
    "        return -1 if uf_alice.num_of_sets * uf_bob.num_of_sets > 1 else res            \n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.father = [None] * (size+1)\n",
    "        self.num_of_sets = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.father[x] is None: return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        self.father[self.find(x)] = self.find(y)\n",
    "        self.num_of_sets -= 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.father = [None] * (size+1)\n",
    "        self.num_of_sets = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.father[x] is None: return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        self.father[self.find(x)] = self.find(y)\n",
    "        self.num_of_sets -= 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        uf_alice = UnionFind(n)\n",
    "        uf_bob = UnionFind(n)\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 3:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 1:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "            if _type == 2:\n",
    "                if not uf_bob.is_connected(n1,n2):\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "\n",
    "        return -1 if uf_alice.num_of_sets * uf_bob.num_of_sets > 1 else res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.father = [None] * (size+1)\n",
    "        self.num_of_sets = size\n",
    "    \n",
    "    def find(self,x):\n",
    "        if self.father[x] is None: return x\n",
    "        self.father[x] = self.find(self.father[x])\n",
    "        return self.father[x]\n",
    "    \n",
    "    def is_connected(self,x,y):\n",
    "        return self.find(x) == self.find(y)\n",
    "    \n",
    "    def merge(self,x,y):\n",
    "        self.father[self.find(x)] = self.find(y)\n",
    "        self.num_of_sets -= 1\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        \n",
    "        uf_alice = UnionFind(n)\n",
    "        uf_bob = UnionFind(n)\n",
    "\n",
    "        for _type,n1,n2 in edges:\n",
    "            #如果此边为共用边, 且alice目前边中n1,n2未连接, 加入此边\n",
    "            if _type == 3:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "        \n",
    "        for _type,n1,n2 in edges:\n",
    "            if _type == 1:\n",
    "                if not uf_alice.is_connected(n1,n2):\n",
    "                    uf_alice.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "            \n",
    "            if _type == 2:\n",
    "                if not uf_bob.is_connected(n1,n2):\n",
    "                    uf_bob.merge(n1,n2)\n",
    "                else:\n",
    "                    res += 1\n",
    "\n",
    "        return -1 if uf_alice.num_of_sets * uf_bob.num_of_sets > 1 else res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.comp_cnt = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1 for _ in range(n)]\n",
    "    def find(self,x):\n",
    "        if self.fa[x]==x:\n",
    "            return self.fa[x]\n",
    "        self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "        return x if self.fa[x]==x else self.find(self.fa[x])\n",
    "    def union(self,x,y)->bool:\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x]<self.sz[y]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "        self.comp_cnt-=1\n",
    "        return True\n",
    "    def connected(self,x,y)->bool:\n",
    "        x = self.findset(x)\n",
    "        y = self.findset(y)\n",
    "        return x==y\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ufa,ufb = UF(n),UF(n)\n",
    "\n",
    "        for i in range(len(edges)):\n",
    "            edges[i][1]-=1\n",
    "            edges[i][2]-=1\n",
    "        ans = 0\n",
    "        for t,x,y in edges:\n",
    "            if t==3:\n",
    "                if not ufa.union(x,y):\n",
    "                    ans+=1\n",
    "                else:\n",
    "                    ufb.union(x,y)\n",
    "        for t,x,y in edges:\n",
    "            if t==1:\n",
    "                if not ufa.union(x,y):\n",
    "                    ans+=1\n",
    "            elif t==2:\n",
    "                if not ufb.union(x,y):\n",
    "                    ans+=1\n",
    "        if ufa.comp_cnt!=1 or ufb.comp_cnt!=1:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        uf = UF(n + 1)\n",
    "        for a in edges:#添加通用边\n",
    "            if a[0] == 3:\n",
    "                if uf.find(a[1]) != uf.find(a[2]):\n",
    "                    uf.union(a[1], a[2])\n",
    "                else:\n",
    "                    ans += 1\n",
    "        uf2 = copy.deepcopy(uf)#复制并查集用于检查andy\n",
    "        for a in edges:#添加andy边\n",
    "            if a[0] == 1:\n",
    "                if uf2.find(a[1]) != uf2.find(a[2]):\n",
    "                    uf2.union(a[1], a[2])\n",
    "                else:\n",
    "                    ans += 1\n",
    "        for a in edges:#添加bob边\n",
    "            if a[0] == 2:\n",
    "                if uf.find(a[1]) != uf.find(a[2]):\n",
    "                    uf.union(a[1], a[2])\n",
    "                else:\n",
    "                    ans += 1\n",
    "        count = 0# 检查是否连通\n",
    "        for i, n in enumerate(uf.p):\n",
    "            if i == n:\n",
    "                if count == 2:\n",
    "                    return -1\n",
    "                count += 1\n",
    "        count = 0\n",
    "        for i, n in enumerate(uf2.p):\n",
    "            if i == n:\n",
    "                if count == 2:\n",
    "                    return -1\n",
    "                count += 1\n",
    "        return ans             \n",
    "class UF:\n",
    "    def __init__(self, N):\n",
    "        self.p = [i for i in range(N)]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        if x == y:\n",
    "            return\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if(x != y):\n",
    "            self.p[x] = self.p[y]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n\n",
    "        self.n = n\n",
    "        self.components = n\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.parent[x] == x:\n",
    "            return x\n",
    "        self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return False\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.parent[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "        self.components -= 1\n",
    "        return True\n",
    "\n",
    "    \n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uni_find = UnionFind(n)\n",
    "        res = 0\n",
    "        for e in edges:\n",
    "            t, u, v = tuple(e)\n",
    "            u, v = u-1, v-1\n",
    "            if t == 3:\n",
    "                if not uni_find.union(u, v):\n",
    "                    res += 1\n",
    "        uni_find_ali = copy.deepcopy(uni_find)\n",
    "        uni_find_bob = uni_find\n",
    "        for e in edges:\n",
    "            t, u, v = tuple(e)\n",
    "            u, v = u-1, v-1\n",
    "            if t == 2:\n",
    "                if not uni_find_bob.union(u, v):\n",
    "                    res += 1\n",
    "            elif t == 1:\n",
    "                if not uni_find_ali.union(u, v):\n",
    "                    res += 1\n",
    "        if uni_find_ali.components == 1 and uni_find_bob.components == 1:\n",
    "            return res\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        fa = list(range(n + 1))\n",
    "        t3ed = []\n",
    "        t1ed = []\n",
    "        t2ed = []\n",
    "        def find(x):\n",
    "            if x != fa[x]: fa[x] = find(fa[x])\n",
    "            return fa[x]\n",
    "        def findb(x):\n",
    "            #print(x, bobset[x])\n",
    "            if x != bobset[x]: bobset[x] = findb(bobset[x])\n",
    "            return bobset[x]\n",
    "        for a, b, c in edges:\n",
    "            if a == 3:\n",
    "                t3ed.append((b, c))\n",
    "            elif a == 1:\n",
    "                t1ed.append((b, c))\n",
    "            else:\n",
    "                t2ed.append((b, c))\n",
    "        ans = 0\n",
    "\n",
    "        for x, y in t3ed:\n",
    "            px, py = find(x), find(y)\n",
    "            if px == py:\n",
    "                ans += 1\n",
    "                continue\n",
    "            fa[px] = py\n",
    "        \n",
    "        bobset = fa.copy()\n",
    "        for x, y in t1ed:\n",
    "            px, py = find(x), find(y)\n",
    "            if px == py:\n",
    "                ans += 1\n",
    "                continue\n",
    "            fa[px] = py\n",
    "        print(bobset)\n",
    "        #print(findb(1))\n",
    "        for x, y in t2ed:\n",
    "            px, py = findb(x), findb(y)\n",
    "            #print(x, y, px, py)\n",
    "            if px == py:\n",
    "                ans += 1\n",
    "                continue\n",
    "            bobset[px] = py\n",
    "        #print(fa, bobset)\n",
    "        cnt = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i == fa[i]:\n",
    "                cnt += 1\n",
    "        if cnt == 0 or cnt > 1: return -1\n",
    "        cnt = 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i == bobset[i]:\n",
    "                cnt += 1\n",
    "        if cnt == 0 or cnt > 1: return -1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parentMap = [i+1 for i in range(n)]\n",
    "        self.groupNum = n\n",
    "        self.size = [1 for _ in range(n)]\n",
    "    def getGroup(self, n):\n",
    "        while self.parentMap[n-1] != n:\n",
    "            n = self.parentMap[n-1]\n",
    "        return n\n",
    "    def union(self, n1, n2):\n",
    "        g1, g2 = self.getGroup(n1), self.getGroup(n2)\n",
    "        if g1 == g2: return\n",
    "        if self.size[g1-1] < self.size[g2-1]:\n",
    "            g1, g2 = g2, g1\n",
    "        self.parentMap[g2-1] = g1\n",
    "        self.size[g1-1] += self.size[g2-1]\n",
    "        self.groupNum-=1\n",
    "        # print(n1, n2, self.parentMap)\n",
    "    def sameGroup(self, n1, n2):\n",
    "        return self.getGroup(n1) == self.getGroup(n2)\n",
    "    def getCopy(self):\n",
    "        newUf = UnionFind(len(self.parentMap))\n",
    "        newUf.parentMap = copy.deepcopy(self.parentMap)\n",
    "        newUf.groupNum = self.groupNum\n",
    "        newUf.size = copy.deepcopy(self.size)\n",
    "        return newUf\n",
    "    \n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        Aedges = []\n",
    "        Bedges = []\n",
    "        Cedges = []\n",
    "        for edge in edges:\n",
    "            newEdge = [edge[1], edge[2]]\n",
    "            if edge[0] == 1:\n",
    "                Aedges.append(newEdge)\n",
    "            elif edge[0] == 2:\n",
    "                Bedges.append(newEdge)\n",
    "            else:\n",
    "                Cedges.append(newEdge)\n",
    "        nodes = [ [] for _ in range(n)]\n",
    "        \n",
    "        uf = UnionFind(n)\n",
    "\n",
    "        usedEdge = 0\n",
    "        for e in Cedges:\n",
    "            if not uf.sameGroup(e[0], e[1]):\n",
    "                usedEdge+=1\n",
    "                uf.union(e[0], e[1])\n",
    "        if uf.groupNum == 1: return len(edges)-usedEdge\n",
    "\n",
    "        Auf = uf.getCopy()\n",
    "        for e in Aedges:\n",
    "            if not Auf.sameGroup(e[0], e[1]):\n",
    "                usedEdge+=1\n",
    "                Auf.union(e[0], e[1])\n",
    "        if not Auf.groupNum == 1: return -1\n",
    "\n",
    "        for e in Bedges:\n",
    "            if not uf.sameGroup(e[0], e[1]):\n",
    "                usedEdge+=1\n",
    "                uf.union(e[0], e[1])\n",
    "        if not uf.groupNum == 1: return -1\n",
    "        return len(edges)-usedEdge    \n",
    "        # AVisited = set(visited)\n",
    "        # Aused = 0\n",
    "        # for e in Aedges:\n",
    "        #     if e[0] not in AVisited or e[1] not in AVisited:\n",
    "        #         AVisited.add(e[0])\n",
    "        #         AVisited.add(e[1])\n",
    "        #         Aused+=1\n",
    "        # if len(AVisited) != n: return -1\n",
    "        # for e in Bedges:\n",
    "        #     if e[0] not in visited or e[1] not in visited:\n",
    "        #         visited.add(e[0])\n",
    "        #         visited.add(e[1])\n",
    "        #         usedEdge+=1\n",
    "        # if len(visited) != n: return -1\n",
    "        # return len(edges)-usedEdge\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UF:\n",
    "    def __init__(self, n):\n",
    "        self.size={i:1 for i in range(n+1)}\n",
    "        self.parent = {i:i for i in range(n+1)}\n",
    "        self.com = n\n",
    "\n",
    "    def find(self, v):\n",
    "        if self.parent[v] != v:\n",
    "            self.parent[v] = self.find(self.parent[v])\n",
    "        return self.parent[v]\n",
    "\n",
    "    def is_connect(self):\n",
    "        return self.com == 1\n",
    "\n",
    "    def union(self, v1, v2):\n",
    "        p1 = self.find(v1)\n",
    "        p2 = self.find(v2)\n",
    "        if p1!=p2:\n",
    "            if self.size[p1]>self.size[p2]:\n",
    "                self.parent[p2] =p1\n",
    "                self.size[p1] += self.size[p2]\n",
    "            else:\n",
    "                self.parent[p1] =p2\n",
    "                self.size[p2] += self.size[p1]\n",
    "            self.com -=1\n",
    "            return True\n",
    "        return False\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        alice, bob =UF(n), UF(n)\n",
    "\n",
    "        res = 0\n",
    "        for t, x, y in edges:\n",
    "            if t==3:\n",
    "                res += alice.union(x,y) and bob.union(x,y)\n",
    "        for t, x,y in edges:\n",
    "            if t ==1:\n",
    "                res +=alice.union(x,y)\n",
    "            elif t ==2:\n",
    "                res += bob.union(x,y)\n",
    "\n",
    "        return len(edges)-res  if alice.is_connect() and bob.is_connect() else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "pa = [[0] * 2 for _ in range(100000)]\r\n",
    "rk = [[0] * 2 for _ in range(100000)]\r\n",
    "cmp = [0, 0]\r\n",
    "\r\n",
    "def find(i: int, k: int) -> int:\r\n",
    "    if pa[i][k] != i:\r\n",
    "        pa[i][k] = find(pa[i][k], k)\r\n",
    "    return pa[i][k]\r\n",
    "\r\n",
    "def join(i: int, j: int, k: int) -> int:\r\n",
    "    f = find(i, k)\r\n",
    "    g = find(j, k)\r\n",
    "    if f == g: return 1\r\n",
    "    \r\n",
    "    if rk[f][k] > rk[g][k]:\r\n",
    "        pa[g][k] = f\r\n",
    "    else:\r\n",
    "        if rk[f][k] == rk[g][k]:\r\n",
    "            rk[g][k] += 1\r\n",
    "        pa[f][k] = g\r\n",
    "\r\n",
    "    cmp[k] -= 1\r\n",
    "    return 0\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\r\n",
    "        for i in range(n):\r\n",
    "            for j in range(2):\r\n",
    "                pa[i][j] = i\r\n",
    "                rk[i][j] = 0\r\n",
    "        cmp[0] = cmp[1] = n\r\n",
    "        \r\n",
    "        edges.sort(key=lambda e: -e[0])\r\n",
    "        res = 0\r\n",
    "        for ty, u, v in edges:\r\n",
    "            if sum(join(u - 1, v - 1, k) << k for k in range(2) if ty >> k & 1) == ty:\r\n",
    "                res += 1\r\n",
    "        \r\n",
    "        return -1 if cmp[0] != 1 or cmp[1] != 1 else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        parents = list(range(n+1))\n",
    "        \n",
    "        def find(x,parents):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x],parents)\n",
    "            return parents[x]\n",
    "\n",
    "        def union(u,v,parents):\n",
    "            x , y = find(u,parents) , find(v,parents)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "        \n",
    "        def isConnect(u,v,parents):\n",
    "            x , y = find(u,parents) , find(v,parents)\n",
    "            return x == y\n",
    "        \n",
    "        ans = 0\n",
    "\n",
    "        for t , u , v in edges:\n",
    "            if t == 3:\n",
    "                if isConnect(u,v,parents):\n",
    "                    ans += 1\n",
    "                    continue\n",
    "                union(u,v,parents)\n",
    "\n",
    "        a_parents = copy.deepcopy(parents)\n",
    "\n",
    "        for t , u , v in edges:\n",
    "            if t == 1:\n",
    "                if isConnect(u,v,a_parents):\n",
    "                    ans += 1\n",
    "                    continue\n",
    "                union(u,v,a_parents)\n",
    "\n",
    "        for t , u , v in edges:\n",
    "            if t == 2:\n",
    "                if isConnect(u,v,parents):\n",
    "                    ans += 1\n",
    "                    continue\n",
    "                union(u,v,parents)\n",
    "        \n",
    "        cnts_a = Counter([find(i,a_parents) for i in range(1,n+1)])\n",
    "        cnts = Counter([find(i,parents) for i in range(1,n+1)])\n",
    "\n",
    "        return -1 if len(cnts_a) * len(cnts) > 1 else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        def union(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "\n",
    "        def is_link():\n",
    "            t = find(1)\n",
    "            for i in range(1, n + 1):\n",
    "                if find(i) != t:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        p = [i for i in range(n + 1)]\n",
    "        ans = 0\n",
    "        for t, u, v in edges:\n",
    "            if t == 3:\n",
    "                if find(u) == find(v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    union(u, v)\n",
    "        tmp = p[::]\n",
    "\n",
    "        for t, u, v in edges:\n",
    "            if t == 1:\n",
    "                if find(u) == find(v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    union(u, v)\n",
    "        if not is_link():\n",
    "            return -1\n",
    "\n",
    "        p = tmp\n",
    "        for t, u, v in edges:\n",
    "            if t == 2:\n",
    "                if find(u) == find(v):\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    union(u, v)\n",
    "        if not is_link():\n",
    "            return -1\n",
    "\n",
    "        return ans\n",
    "\n",
    "                                                                      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class DSU:\n",
    "    def __init__(self, n):\n",
    "        self.data= [i for i in range(n+1)]\n",
    "        self.cnt = n \n",
    "    def find(self, x):\n",
    "        if x == self.data[x]:\n",
    "            return x \n",
    "        else:\n",
    "            self.data[x] = self.find(self.data[x]) \n",
    "            return self.data[x] \n",
    "    def un(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx ==fy:\n",
    "            return False \n",
    "        else:\n",
    "            self.data[fy] = fx \n",
    "            self.cnt -= 1\n",
    "            return True \n",
    "    \n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        dsu1 = DSU(n)\n",
    "        dsu2 = DSU(n) \n",
    "        cut = 0 \n",
    "        for t, a, b in edges:\n",
    "            if t == 3:\n",
    "                if not dsu1.un(a,b):\n",
    "                    cut += 1\n",
    "                dsu2.un(a,b)\n",
    "\n",
    "        for t, a, b in edges:\n",
    "            if t == 1:\n",
    "                if not dsu1.un(a, b):\n",
    "                    cut += 1 \n",
    "            elif t == 2:\n",
    "                if not dsu2.un(a, b):\n",
    "                    cut += 1 \n",
    "        if dsu1.cnt > 1 or dsu2.cnt > 1:\n",
    "            return -1 \n",
    "        return cut "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, size):\n",
    "        self.roots = list(range(size))\n",
    "        self.ranks = [0]*size\n",
    "        self.groups = size\n",
    "    \n",
    "    def find(self, x):\n",
    "        if self.roots[x] == x:\n",
    "            return x\n",
    "        self.roots[x] = self.find(self.roots[x])\n",
    "        return self.roots[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootx, rooty = self.roots[x], self.roots[y]\n",
    "        if rootx != rooty:\n",
    "            if self.ranks[rootx] < self.ranks[rooty]:\n",
    "                self.roots[rooty] = rootx\n",
    "            elif self.ranks[rootx] > self.ranks[rooty]:\n",
    "                self.roots[rootx] = rooty\n",
    "            else:\n",
    "                self.roots[rooty] = rootx\n",
    "                self.ranks[rootx] += 1\n",
    "            self.groups -= 1\n",
    "    \n",
    "    @property\n",
    "    def numgroups(self):\n",
    "        return self.groups\n",
    "    \n",
    "    def copy(self):\n",
    "        uf = UnionFind(len(self.roots))\n",
    "        uf.roots = self.roots.copy()\n",
    "        uf.ranks = self.ranks.copy()\n",
    "        uf.groups = self.groups\n",
    "        return uf\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        类似于最小生成树\n",
    "        \"\"\"\n",
    "        numedges = len(edges)\n",
    "        if numedges < n-1:\n",
    "            return -1\n",
    "\n",
    "        edges = collections.deque(sorted(edges, key=lambda x:-x[0]))\n",
    "\n",
    "        visnumedges = 0\n",
    "        uf = UnionFind(n)\n",
    "        \n",
    "        # 优先选择type=3的边\n",
    "        while uf.numgroups > 1 and edges and edges[0][0] == 3:\n",
    "            _, a, b = edges.popleft()\n",
    "            a, b = a-1, b-1\n",
    "            if uf.find(a) == uf.find(b):\n",
    "                continue\n",
    "            visnumedges += 1\n",
    "            uf.union(a, b)\n",
    "\n",
    "        if uf.numgroups == 1:\n",
    "            return numedges - visnumedges\n",
    "        \n",
    "\n",
    "        # 填充type=2的边\n",
    "        nwuf = uf.copy()\n",
    "        while nwuf.numgroups > 1 and edges and edges[0][0] == 2:\n",
    "            _, a, b = edges.popleft()\n",
    "            a, b = a-1, b-1\n",
    "            if nwuf.find(a) == nwuf.find(b):\n",
    "                continue\n",
    "            visnumedges += 1\n",
    "            nwuf.union(a, b)\n",
    "        \n",
    "        if nwuf.numgroups > 1:\n",
    "            return -1\n",
    "\n",
    "        # 填充type=1的边\n",
    "        while edges and edges[0][0] == 2:\n",
    "            edges.popleft()\n",
    "        while uf.numgroups > 1 and edges:\n",
    "            _, a, b = edges.popleft()\n",
    "            a, b = a-1, b-1\n",
    "            if uf.find(a) ==  uf.find(b):\n",
    "                continue\n",
    "            visnumedges += 1\n",
    "            uf.union(a, b)\n",
    "        \n",
    "        if uf.numgroups > 1:\n",
    "            return -1\n",
    "        \n",
    "        return numedges - visnumedges\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.p1 = list(range(n))\n",
    "        self.p2 = list(range(n))\n",
    "    \n",
    "    def union(self, idx1, idx2, t):\n",
    "        if t != 2:\n",
    "            self.p1[self.find1(idx2)] = self.find1(idx1)\n",
    "        if t != 1:\n",
    "            self.p2[self.find2(idx2)] = self.find2(idx1)\n",
    "        \n",
    "    def find1(self, idx):\n",
    "        if self.p1[idx] != idx:\n",
    "            self.p1[idx] = self.find1(self.p1[idx])\n",
    "        return self.p1[idx]\n",
    "    \n",
    "    def find2(self, idx):\n",
    "        if self.p2[idx] != idx:\n",
    "            self.p2[idx] = self.find2(self.p2[idx])\n",
    "        return self.p2[idx]\n",
    "\n",
    "class Solution:\n",
    "    def maxNumEdgesToRemove(self, n: int, edges: List[List[int]]) -> int:\n",
    "        union = UnionFind(n)\n",
    "        edges.sort(key=lambda x: -x[0])\n",
    "        res = 0\n",
    "        for t, a, b in edges:\n",
    "            if t == 1 and union.find1(a-1) == union.find1(b-1):\n",
    "                res += 1\n",
    "            elif t == 2 and union.find2(a-1) == union.find2(b-1):\n",
    "                res += 1\n",
    "            elif t == 3 and union.find1(a-1) == union.find1(b-1):\n",
    "                res += 1\n",
    "            else:\n",
    "                union.union(a-1, b-1, t)\n",
    "        p1 = union.find1(0)\n",
    "        p2 = union.find2(0)\n",
    "        for i in range(1, n):\n",
    "            if union.find1(i) != p1:\n",
    "                return -1\n",
    "            if union.find2(i) != p2:\n",
    "                return -1\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
